#include <iostream>
#include <ctime>
#include "Graph.h"
#include <vector>
#include <queue>
#include <stack>

using namespace std;

Graph::Graph():summit_nb(0),edges_nb(0) { //cerr<<"Constructeur par défaut de Graph"<<endl;
}

Graph::Graph(summit_t n, edges_t m):summit_nb(n),edges_nb(m) { //cerr<<"Constructeur paramétré de Graph"<<endl;
}

void Graph::fill(){
  summit_t n = getSummitNb();
  edges_t m = getEdgesNb();
  
  if((n > 1) && (m >= 1)){
    if (m > (edges_t)(n*(n-1)))
    {
      cerr<<"Graphe impossible à réaliser : nombre d'arêtes trop élevé"<<endl;
      return;
    }
    summit_t max_path_len = (n < m-1)?n:m-1; //Le nombre de sommets du chemin est le minimum entre le nombre de sommets et le nombre d'arêtes moins une
    
    summit_t path_len = rand()%(max_path_len-2)+2; //Génération aléatoire du nombre de sommets dans le chemin(compris entre 2 et min(n, m-1))
    // cout<<"Construction d'un chemin de "<<path_len<<" sommets"<<endl;

    summit_t cpt_s = 0;//Nombre de sommets dans notre graphe
    edges_t cpt_e = 0; //Nombre d'arêtes dans notre graphe
    bool * already_seen = new bool[n] ;//Table des sommets déjà vu. Au départ on ne connait rien.
    for(int i = 0; i < n; ++i){
      already_seen[i] = false;
    }
    //Initialisation : création d'un chemin de s à p
    already_seen[0] = true; //Début du chemin : s
    summit_t summit;
    summit_t tmp =  0;//Permet de stocker le sommet précédent dans le chemin, inialisé à 0 (s)
    for (int i = 1; i < path_len - 2; ++i){ //On tire au sort des sommets qui componseront le chemin en les connectant de la sorte : le 2e au 3e, le 3e au 4e, etc. jusqu'à avoir avant avant dernier et avant dernier (s -> 2e et avant dernier -> p est déjà fait)
      summit = rand()%(n-2)+1; //On tire au sort un sommet entre 1 et n-2 (on peut exclure a priori s et p donc 0 et n-1)
      while (already_seen[summit]){
	summit = (summit+1)%(n-2); //On évite les doublons. Pour ne pas trop boucler en aléatoire, on incrémente de 1 si la première position était occupée
      }
      connect(tmp, summit);
      already_seen[summit] = true;
      tmp = summit;
    }
    connect(tmp, n-1); //On relie l'avant dernier sommet à p
    already_seen[n-1] = true;
    cpt_s = path_len - 1;
    cpt_e = path_len - 1; //On a construit un chemin de taille path_len entre s et p, on a donc utilisé path_len-1 arêtes

    /*
     * Premier chemin de s à t généré.
     * On construit maintenant le reste des arêtes.
     */
    
    //Remplissage : on tire au sort tant que le nombre d'arêtes ou le nombre de sommets ne soit pas atteint.
    //Si sommet jamais vu : on ajoute une arête vers un sommet et on incrémente cpt_s et cpt_e
    //Si sommet déjà vu : on ajoute une arête vers un sommet  et on incrémente que cpt_e

    summit_t neighbour;
    while((cpt_e < m)){
      summit = rand()%(n-1); //Source de l'arête à ajouter : ne peut pas être p donc valeur comprise entre 0 et n-2
      while(not already_seen[summit] ) { //on sélectionne un sommet déjà vu
	summit=(summit+1)%(n-1);
      }
      neighbour = rand()%(n-1)+1; //Destination de l'arête à ajouter : ne peut pas être s donc valeur comprise entre 1 et n-1
      while (neighbour==summit || neighbour==0)
      {
	neighbour=(neighbour+1)%(n-1);
      }
      if(cpt_s < n){ //Si il reste des points à placer : on prend un nouveau sommet pour neighbour
	while (already_seen[neighbour]) {
	  neighbour=(neighbour+1)%(n-1);
	}
	already_seen[neighbour]=true;
	++cpt_s; //On voit un nouveau sommet
      }
      if(not areConnected(summit, neighbour)) {
	connect(summit, neighbour);
	++cpt_e;
      }
    }
    delete [] already_seen;
  }
  else {
    cerr<<"Erreur dans les valeurs des paramètres du remplissage de Graph\n";
    cerr<<"Nombre arêtes attendu ≥ 1, reçu "<<m<<". Nombre de sommets attendu ≥ 2, reçu "<<n<<endl;
    exit(1);
  }
}

Graph::Graph(Graph &g):summit_nb(g.getSummitNb()),edges_nb(g.getEdgesNb())
{
  cout<<"Construction par copie du graphe de "
      <<summit_nb<<" sommets et "
      <<edges_nb<<" arêtes."<<endl;
}

Graph::~Graph() {}

summit_t Graph::getSummitNb() const
{
  return summit_nb;
}

void Graph::setSummitNb(summit_t n)
{
  summit_nb=n;
}

edges_t Graph::getEdgesNb() const
{
  return edges_nb;
}

void Graph::setEdgesNb(edges_t m)
{
  edges_nb=m;
}


bool belongsTo(summit_t summit, summit_t* summits, summit_t size){
  summit_t i = 0;
  while(i < size){
    if(summits[i] == summit){
      return true;
    }
    ++i;
  }
  return false;
}

vector<summit_t> * Graph::shortestPath(summit_t a, summit_t b) const
{
  if (a==b)
  {
    return NULL;
  }
  
  summit_t * father = new summit_t [summit_nb];
  for (int k(0); k<summit_nb; k++)
  {
    father[k]=(summit_t)-1;
  }
  vector<summit_t> * neighbours;
  queue<summit_t> * s_queue = new queue<summit_t>;
  bool foundPath=false;
  summit_t s_temp;

  s_queue->push(a); //Ajout du sommet source à la liste
  father[a] = a;
  while ((not s_queue->empty()) && (not foundPath))
  {
    s_temp = s_queue->front(); s_queue->pop(); //Récupère le premier élément de la file, puis le supprime
    neighbours = getNeighbours(s_temp);
    for (size_t k(0); k<neighbours->size(); k++)
    {
      if (father[neighbours->at(k)] == (summit_t)-1) //Si l'on a jamais vu le sommet
      {
	father[neighbours->at(k)]=s_temp;
	s_queue->push(neighbours->at(k));
	if (neighbours->at(k) == b) //Si c'est le sommet d'arrivée
	{
	  foundPath=true;
	  break; //On quitte la boucle for
	}
      }
    }
    delete neighbours; //On désalloue la mémoire allouée par la méthode getNeighbours()
  }
  
  vector<summit_t> * path=NULL;
  stack<summit_t> * s_stack=NULL;
  
  if (foundPath)
  {
    path = new vector<summit_t>;
    s_stack = new stack<summit_t>;
    
    s_stack->push(b);
    do
    {
      s_stack->push(father[s_stack->top()]); //Ajout du père de l'élément précédent
    } while (s_stack->top() != a);
    
    while (not s_stack->empty())
    {
      path->push_back(s_stack->top());
      s_stack->pop();
    }
    delete s_stack;
  }
    
  delete [] father;
  delete s_queue;
  if ((path!=NULL) && (path->size()>1)) //On envoie le vecteur seulement s'il n'est pas vide
    return path;
  if (path!=NULL)
    delete path;
  return NULL;
}

vector<summit_t> * Graph::shortestPath() const
{
  return shortestPath(0,summit_nb-1); //s = 0 et t = (nombre de sommets - 1)
}

vector<summit_t> * Graph::onePath(summit_t a, summit_t b) const
{
  if (a==b)
  {
    return NULL;
  }

  bool found_path=false;
  stack<summit_t> * s_stack = new stack<summit_t>;
  summit_t s_temp;
  vector<summit_t> * neighbours;
  summit_t * father = new summit_t [summit_nb];
  for (summit_t i=0; i<summit_nb; i++)
  {
    father[i]=(summit_t)-1;
  }

  father[a] = a;
  s_stack->push(a);
  while ((not s_stack->empty()) && (not found_path))
  {
    s_temp = s_stack->top(); s_stack->pop();
    neighbours = getNeighbours(s_temp);
    for (size_t i=0; i<neighbours->size(); i++)
    {
      if (father[neighbours->at(i)] == (summit_t)-1) //Sommet jamais vu
      {
	s_stack->push(neighbours->at(i));
	father[neighbours->at(i)]=s_temp;
	if (neighbours->at(i) == b)
	{
	  found_path=true;
	  break;
	}
      }
    }
    delete neighbours;
  }

  vector<summit_t> * path = NULL;
  while (not s_stack->empty())
    s_stack->pop();
  
  if (found_path)
  {
    path = new vector<summit_t>;
    
    s_stack->push(b);
    do
    {
      s_stack->push(father[s_stack->top()]); //Ajout du père de l'élément précédent
    } while (s_stack->top() != a);
    
    while (not s_stack->empty())
    {
      path->push_back(s_stack->top());
      s_stack->pop();
    }
  }
    
  delete [] father;
  delete s_stack;
  if ((path!=NULL) && (path->size()>1)) //On envoie le vecteur seulement s'il n'est pas vide
  {
    return path;
  }
  if (path!=NULL)
    delete path;
  return NULL;
  
  return path;
}

vector<summit_t> * Graph::onePath() const
{
  return onePath(0,summit_nb-1);
}


vector<summit_t> * Graph::getNeighbours(summit_t v) const
{
  vector<summit_t> * neighbours = new vector<summit_t>;
  if ((v<getSummitNb()) || (v>=0))
  {
    for (summit_t i=0; i<getSummitNb(); i++)
    {
      if (areConnected(v,i))
	neighbours->push_back(i);
    }
  }
  return neighbours;
}

/*vector<summit_t> * Graph::isNeighbourOf(summit_t v) const
{
  vector<summit_t> * neighbours = new vector<summit_t>;
  if ((v<getSummitNb()) || (v>=0))
  {
    for (summit_t i=0; i<getSummitNb(); i++)
    {
      if (areConnected(i,v))
	neighbours->push_back(i);
    }
  }

  return neighbours;
  }*/

edges_t Graph::degreeOf(summit_t v) const
{
  edges_t d=0;
  for (summit_t i=0; i<getSummitNb(); i++)
  {
    if (areConnected(i,v) || areConnected(v,i))
    {
      d++;
    }
  }
  return d;
}
